package datastruct.set;

import java.util.Arrays;

/**
    * @author wangc
    * 并查集
    * @date 2021/6/15 下午 8:23
*/
public class UnionSet {


    public static void main(String[] args) {

        UnionSet us = new UnionSet(6);
        us.parent[0] = 1;
        us.parent[1] = 2;
        us.parent[2] = 3;
        us.parent[4] = 2;
        us.parent[5] = 4;
        System.out.println(Arrays.asList(us.parent));
        us.findAndCompress(0);
        System.out.println(Arrays.asList(us.parent));
        System.out.println();
    }


    public int[] parent;

    /**
        * @param n 并查集元素个数
        * @desc UnionSet
    */
    public UnionSet(int n) {
        this.parent = new int[n];
        for (int i = 0; i < n; i++) {
            this.parent[i] = i;
        }
    }


    public int findRoot(int x){
        if(x==parent[x]) return x;
        return findRoot(parent[x]);
    }

    /**
        * @param x
    	* @param y
        * @return int:x所在集合的根节点
        * @desc merge:把y所在集合合并到x所在集合
    */
    public int merge(int x, int y){
        int yRoot = findRoot(y);
        int xRoot = findRoot(x);
        parent[yRoot] = xRoot;
        return xRoot;
    }

    /**
        * @param x
        * @return int
        * @desc 路径压缩，将x的父节点设为根节点，会把x到x的根节点上所有节点的父节点设为根节点
     * 主要思想就是先把父节点压缩,再把自己指向父节点的父节点,即根节点
    */
    public int findAndCompress(int x){
        if(x==parent[x]) return x;
        parent[x] = findAndCompress(parent[x]);
        return parent[x];
    }
}
